4420. Корень кубического уравнения

Дано кубическое уравнение

ax³ + bx² + cx + d = 0 (a ≠ 0)

Известно, что у этого уравнения ровно один корень. Найдите его.

Вход. Четыре целых числа a, b, c, d (−1000 ≤ a, b, c, d ≤ 1000).

Выход. Выведите единственный корень уравнения с точностью не менее 6 десятичных знаков.

Пример входа	Пример выхода
-1 -6 -12 -7	-1.0000000111

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Локализируем корень равнения f(x) = 0. Для этого найдем такое r, что f(-r) * f(r) < 0. Например, инициализировав r = 1, будем на каждом шаге увеличивать r в два раза пока не будет выполняться неравенство f(-r) * f(r) < 0. Таким образом будем перебирвать интервалы [-1; 1], [-2; 2], [-4; 4], [-8; 8], …. пока не найдем интервал в котором лежит корень уравнения.

Положим l = -r. Далее на промежутке [l; r] при помощи бинарного поиска (деления отрезка пополам) ищем корень.

Реализация алгоритма

Объявим константу епсилон.

.

#define EPS 1e-12

Объявим функцию, вычисляющую кубический многочлен.

double f(double x)

{

return a*x*x*x + b*x*x + c*x + d;

}

Основная часть программы. Читаем входные данные.

scanf("%lf %lf %lf %lf",&a,&b,&c,&d);

Находим границы [l; r], в которых лежит искомый корень. Положим изначально r = 1. Будем последовательно увеличивать r в два раза, пока искомый корень не будет находиться в промежутке [-r; r] (для этого необходимо, чтобы функция f(x) принимала противоположные по знаку значения на концах интервала). После чего положим l = -r.

r = 1;

while(f(r) * f(-r) >= 0) r *= 2;

l = -r;

При помощи бинарного поиска ищем корень уравнения f(x) = 0 на промежутке [l; r].

while (r - l > EPS)

{

x = (l + r) / 2;

if (f(x) * f(r) > 0) r = x; else l = x;

}

Выводим ответ.

printf("%.8lf\n",l);

Java реализация

import java.util.*;

public class Main

{

static double a, b, c, d;

static double f(double x)

{

return a*x*x*x + b*x*x + c*x + d;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

a = con.nextDouble();

b = con.nextDouble();

c = con.nextDouble();

d = con.nextDouble();

double right = 1;

while(f(right) * f(-right) >= 0) right *= 2;

double left = -right;

while (right - left > 1e-6)

{

double middle = (left + right) / 2;

if (f(middle) * f(right) > 0) right = middle;

else left = middle;

}

System.out.println(left);

con.close();

}

}